package j2024.j202410;

import java.util.ArrayList;
import java.util.Arrays;

public class j1011 {
    /**
     *
     56. 合并区间
     以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
     请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(a, b)->{
            return a[0]-b[0];
        });
        int n = intervals.length;
        int left = intervals[0][0],right = intervals[0][1];
        ArrayList<int[]> ret = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            int a = intervals[i][0],b = intervals[i][1];
            if(right>=a){
                right = Math.max(right,b);
            }else {
                ret.add(new int[]{left,right});
                left = a;right = b;
            }
        }
        ret.add(new int[]{left,right});
        return ret.toArray(new int[0][]);
    }
    public int[][] merge2(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->{
            return a[0]-b[0];
        });
        int left = intervals[0][0],right = intervals[0][1];
        int len = intervals.length;
        ArrayList<int[]> ret = new ArrayList<>();
        for (int i = 1; i < len; i++) {
            int a = intervals[i][0],b = intervals[i][1];
            if(right>=a){
                right = Math.max(right,b);
            }else {
                ret.add(new int[]{left,right});
                left = a;right=b;
            }
        }
        ret.add(new int[]{left,right});
        return ret.toArray(new int[0][]);
    }
}
